"Between the devil and the deep blue sea" is an idiom meaning a dilemma—i.e., to choose between two undesirable situations (equivalent to "between a rock and a hard place").
The phrase may have been a nautical reference to the deep blue sea and a "devil", a seam (where two hull planks meet) that is difficult to reach on a ship. It may have been a reference to being a member of the lower deck or crew of a sailing ship in the English Navy. Such sailors were often pressed into service unwillingly. One who was "between the devil and the deep blue sea" would literally be beneath the upper deck (officer territory) and thus a member of the crew.
Another possible origin involves the fact that "devil" was a name for the longest seam of a wooden ship,[1] which ran from the bow to the stern. When at sea and the devil had to be caulked, the sailor sat in a bosun's chair to do so. He was suspended between the devil and the sea, a very precarious position, especially when the ship was underway. If sailors fell from a footrope under a yardarm, they would either land on the deck (within the devil plank) or in the water (outside of the devil plank). Either option is likely fatal.
However, this nautical origins is unlikely. This is because the first recorded citation of "the Devil and the deep sea" in print is in Robert Monro's His expedition with the worthy Scots regiment called Mac-keyes, 1637: "I, with my partie, did lie on our poste, as betwixt the devill and the deep sea." Because the nautical use of the word "devil" as mentioned above cannot be confirmed until more than two centuries later, the nautical origin seems improbable.